【知识框架】
图的基本概念
    一、图的定义
        图是一种由像素块组成的矩阵，图结构是由节点和边组成的。
    二、图的基本概念和术语
    1、有向图
        若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。
    2、无向图
        若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。
    3、简单图
        ①不存在重复边;②不存在顶点到自身的边
    4、多重图
        多重图是允许存在多条边连接相同一对顶点的图。在多重图中，顶点之间可以有多条重复的边，这些边可能代表不同的关系、权重或其他属性。
    5、完全图（也称简单完全图）
        对于无向图，∣ E ∣ |E|∣E∣的取值范围是0 00到n ( n − 1 ) / 2 n(n-1)/2n(n−1)/2，有n ( n − 1 ) / 2 n(n -1)/2n(n−1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，∣ E ∣ |E|∣E∣的取值范围是0 00到n ( n − 1 ) n(n-1)n(n−1)，有n ( n − 1 ) n(n-1)n(n−1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
    6、子图
        满足V ( G ′ ) = V ( G )  则G'是G的生成子图。
    7、连通、连通图和连通分量
        连通 描述的是顶点之间的可达性。
        连通图 是一种特殊的图，所有顶点彼此连通。
        连通分量 是图中连通顶点的最大集合，一个图可以由多个连通分量组成
    8、强连通图、强连通分量
        在有向图中，若从顶点v vv到顶点w ww和从顶点w ww到项点v vv之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，
    9、生成树、生成森林
        生成树 是一种特殊的子图，包含图中所有的顶点，并且是无环的连通子图。简单来说，生成树是原图的一个连通子图，它包含了图的所有顶点，但只包含足够的边来保持连通性且没有环。
        生成森林 是一个图的生成树的集合，适用于不连通的图。在一个不连通的图中，每个连通分量都可以有自己的生成树，这些生成树的集合构成了生成森林。
    10、顶点的度、入度和出度
        顶点的度：在无向图中，表示连接到该顶点的所有边的数量。
        入度：在有向图中，表示指向该顶点的边的数量。
        出度：在有向图中，表示从该顶点出发的边的数量
    11、边的权和网
        在一个图中每条边上都可以标注一个数值，成为权值，这种边上有权值的图成为加权图或网
    12、稠密图、稀疏图
        稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。
    13、路径、路径长度和回路
        路径：顶点之间的一个序列，其中每对相邻顶点通过边连接。
        路径长度：路径中的边的数量，或在有权图中，路径中边的权重之和。
        回路：起点和终点是同一个顶点的路径，其中除起点外没有重复顶点。
    14、 简单路径、简单回路
        在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
    15、距离
        从顶点u uu出发到顶点v vv的最短路径若存在，则此路径的长度称为从u uu到v vv的距离。若从u uu到v vv根本不存在路径，则记该距离为无穷( ∞ ) 。
    16、有向树
        一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。
图的存储结构
    一、邻接矩阵
        邻接矩阵是图论中用于表示图（Graph）结构的一种重要数据结构，特别适用于表示顶点之间连接关系的图形。
        图的邻接矩阵 可以用于无向图和有向图，矩阵的元素表示图中顶点之间是否存在边或边的权重。
        邻接矩阵表示法的优缺点

        优点：
            直观、简单、好理解
            方便检查任意一对顶点间是否存在边
            方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
            方便计算任一顶点的“度”。
        缺点：
            不便于增加和删除顶点
            浪费空间——存稀疏图(点很多而边很少)有大量无效元素
            对稠密图(特别是完全图)还是很合算的
            浪费时间——统计稀疏图中一共有多少条边

    二、邻接表   '''http://t.csdnimg.cn/nz3Vw'''   顺序存储+链式存储
        邻接表是一种用于表示图的常见数据结构，尤其适用于稀疏图（边的数量远小于顶点数量平方的图）。与邻接矩阵不同，邻接表在存储空间上更为节省，因为它只存储实际存在的边。
    三、十字链表
        十字链表（Orthogonal List 或 Cross Linked List）是一种用于表示有向图的扩展邻接表数据结构，它同时结合了邻接表和逆邻接表的特点，用来更高效地表示和操作有向图。十字链表在每个节点中包含了指向其邻接节点和逆邻接节点的指针，从而使得在图中进行各种操作（如遍历、插入、删除）更为方便
    四、邻接多重表
         邻接多重表是一种用于处理多重边的图的表示方法，它在传统邻接表的基础上进行了扩展，通过链表结构来管理每个顶点的多条边信息。这种结构能够有效地表示和处理有多重边的图，并支持图的动态操作。
    五、边集数组
        边集数组（Edge List）是一种图的表示方式，它使用一个数组（或列表）来存储图中的所有边。每条边由一对顶点（在无向图中）或三元组（在有向图中，包括起始顶点、目标顶点和权重）来表示。边集数组非常简单，适用于图的边数相对较少的情况，或者需要快速存取边的信息时。


图的遍历
    一、深度优先遍历http://t.csdnimg.cn/dDzVh
    https://visualgo.net/zh/dfsbfs?slide=7-11
    1、DFS算法
    探索路径：从起始节点开始，DFS 会沿着每一条可能的路径不断向前深入，直到找到一个未访问的节点或者走到路径的尽头（没有未访问的邻居节点）。
    回溯：当到达没有未访问邻居节点的节点时，算法回溯到前一个节点，并继续沿其他未访问的路径进行搜索。
    递归或栈实现：DFS 可以通过递归方式实现，也可以使用栈来模拟递归过程。
    2、DFS算法的性能分析
    3、深度优先的生成树和生成森林
    深度优先生成树：在连通图中，DFS 遍历得到一棵树，包含所有节点和部分边，不包含环。
    深度优先生成森林：在非连通图中，DFS 遍历每个连通分量，得到多棵生成树，组成森林。
    二、广度优先遍历
    1、BFS算法
    广度优先搜索（BFS，Breadth-First Search） 是一种图搜索算法，用于遍历或搜索图或树的数据结构。它通过层次遍历的方式，逐层扩展节点，首先访问距离起始节点最近的节点，然后逐步深入到更远的节点。

    2、BFS算法性能分析
    三、图的遍历与图的连通性

        图的遍历包括两种主要方法：
        深度优先搜索（DFS）：深入到一个节点的所有邻居，直到没有未访问的邻居为止，再回溯。
        广度优先搜索（BFS）：按照层次进行遍历，逐层扩展。
        图的连通性是指在一个无向图中，是否能从任意节点到达其他节点。如果图中任何两个节点都可以连通，则该图是连通图。如果不能，图中各个连通子集被称为连通分量。在有向图中，若从任意节点都可以到达其他节点，称为强连通图。

    最小生成树:是一个无环的树结构。所有边的权重之和最小。
    一、普里姆（Prim）算法
    Prim 算法是一种贪心算法，用于寻找连通加权无向图的最小生成树。它通过逐步扩展树的节点和边，始终选择能够最小化当前树与剩余节点之间连接的最小边。
    Prim 算法步骤：
    初始化一个节点作为树的起点，将其标记为已访问。
    查找所有与生成树中已访问节点相连接的未访问节点，选择权重最小的边，将该边加入生成树。
    将边连接的另一个节点加入生成树，并标记为已访问。
    重复步骤 2 和 3，直到生成树包含所有节点。

    二、克鲁斯卡尔（Kruskal）算法
    Kruskal 算法也是一种贪心算法，它不同于 Prim 算法的逐步扩展方式。Kruskal 算法每次从全图中选取权重最小的边，并将其加入生成树中，只要这条边不会形成环。
    Kruskal 算法步骤：
    将图中的所有边按权重升序排序。
    初始化时，将每个节点视为一个独立的连通分量（森林结构）。
    按权重顺序选择边，若该边连接的两个节点属于不同的连通分量，则将该边加入生成树，并合并这两个连通分量。
    重复步骤 3，直到生成树包含 V-1 条边（其中 V 是图的节点数）

    最短路径
    一、迪杰斯特拉( Dijkstra )算法
    Dijkstra 算法用于解决单源最短路径问题，即从给定的起点（源点）到图中其他所有节点的最短路径。它适用于无向图或有向图，但要求图的权重为非负。
    Dijkstra 算法步骤：
    初始化：
    设定起点的距离为 0，其他所有节点的距离为无穷大。
    将所有节点标记为未访问，并创建一个优先队列（最小堆）存储节点及其距离。
    每次从未访问节点中选择距离起点最近的节点，将其标记为已访问。
    更新该节点所有邻居节点的最短距离：若通过该节点到邻居节点的距离小于当前已知的最短距离，则更新邻居节点的距离。
    重复步骤 2 和 3，直到所有节点都被访问。

    二、弗洛伊德( Floyd )算法
    Floyd-Warshall 算法是一种动态规划算法，用于计算所有节点对之间的最短路径。与 Dijkstra 算法只计算从一个源点到其他节点的最短路径不同，Floyd 算法能同时计算出所有节点对之间的最短路径。它可以处理有向图和无向图，并且可以应对带有负权边的情况（但不能有负环）。
    Floyd 算法步骤：
    初始化距离矩阵 dist，其中 dist[i][j] 是节点 i 到节点 j 的直接距离。如果 i 到 j 之间没有直接边，则初始化为无穷大。
    对于每一个中间节点 k，更新所有节点对 i 和 j 之间的距离，使得 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。即通过节点 k 作为中间节点，看看是否可以找到更短的路径。
    重复该过程，直到所有节点对之间的最短路径都被计算出来。
    拓扑排序
    一、定义
    有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。
    二、算法
    Kahn 算法通过不断选择入度为 0 的节点来进行排序。步骤如下：

    计算图中每个节点的入度（指向该节点的边的数量）。
    将所有入度为 0 的节点加入队列。
    从队列中取出一个入度为 0 的节点，将其加入拓扑序列中，同时移除该节点的所有边，并更新其邻居节点的入度。
    如果某个邻居节点的入度变为 0，将其加入队列。
    重复上述过程，直到队列为空。

最短路径：
一、定义
关键路径是项目管理中用于分析和表示项目计划中的一组活动的顺序，并确定项目的最早完成时间。关键路径上的活动必须按顺序完成，任何一个活动的延迟都会直接导致整个项目的延迟。因此，关键路径的长度决定了项目的最短完成时间。
在图论中，关键路径可以看作是一个加权有向图中的最长路径问题，其中每个节点表示一个任务，边表示任务的依赖关系，权重表示任务的持续时间。
关键路径法（Critical Path Method, CPM）**通常用于计划和控制项目，它的目标是确定项目中哪些任务是关键的，即必须按时完成的任务。

二、算法
关键路径的计算主要基于 AOE 网（活动有向边网，Activity on Edge Network），其中任务是图中的边，节点表示事件。算法通过计算最早开始时间和最迟开始时间来找出关键路径。
关键路径算法步骤：
构建 AOE 网：将所有任务及其依赖关系表示为加权有向图。计算最早时间（Early Time, ET）：对所有节点进行拓扑排序。从源节点开始，按照拓扑排序的顺序，依次计算每个节点的最早发生时间（即该节点所有前驱节点的最早时间加上边的权重）。最早开始时间公式：𝐸𝑇(𝑣)=max⁡(𝐸𝑇(𝑢)+𝑤(𝑢,𝑣))ET(v)=max(ET(u)+w(u,v))其中，𝑤(𝑢,𝑣)w(u,v) 是从节点 𝑢u 到节点 𝑣v 的边的权重。计算最迟时间（Late Time, LT）：从汇节点（终点）开始，按照逆拓扑排序的顺序，依次计算每个节点的最迟发生时间（即该节点所有后继节点的最迟时间减去边的权重）。最迟开始时间公式：𝐿𝑇(𝑣)=min⁡(𝐿𝑇(𝑢)−𝑤(𝑣,𝑢))LT(v)=min(LT(u)−w(v,u))计算关键路径：关键路径上的任务具有相同的最早开始时间和最迟开始时间。即对于节点 𝑣v，若 𝐸𝑇(𝑣)=𝐿𝑇(𝑣)
ET(v)=LT(v)，则该任务位于关键路径上。项目的最短完成时间即为图的最长路径的长度。